package 第一章基础算法.归并排序.id788逆序对的数量;

import java.util.Scanner;

public class Main {
    static long res = 0;
    public static void main(String[]args){
        //处理输入
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[]nums = new int[n];
        for(int i = 0;i<n;i++){
            nums[i] = scanner.nextInt();
        }
        //归并排序过程中统计逆序对数量
        mergeSort_cnt(nums,0,n-1);
        //处理输出
        System.out.println(res);

    }

    public static void mergeSort_cnt(int[]nums,int l ,int r){
        if(l >= r)return;
        int mid = l + (r-l>>1);
        mergeSort_cnt(nums,l,mid);
        mergeSort_cnt(nums,mid+1,r);

        int p1 = l;
        int p2 = mid+1;
        int[]help = new int[r-l+1];
        int k = 0;

        while (p1 <= mid && p2 <= r){
            if(nums[p1] <= nums[p2]){
                help[k++] = nums[p1++];
            }else { //产生了逆序对
                //逆序对数量统计
                res += mid-p1+1;
                help[k++] = nums[p2++];
            }
        }
        while (p1 <= mid){
            help[k++] = nums[p1++];
        }
        while (p2 <= r){
            help[k++] = nums[p2++];
        }

        for(int i = 0;i<help.length;i++){
            nums[l+i] = help[i];
        }
    }
}